package demo6;

import javax.sound.midi.Soundbank;
import java.util.*;

public class Solution {

    //1.剑指 Offer II 020. 回文子字符串的个数(动态规划)
    public int countSubstrings(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int count = 0;
        for(int i = 0; i < len; i++) {
            for(int j = 0; j <= i; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    if(i - j <= 1) {
                        dp[i][j] = true;
                        count++;
                    } else if(dp[i - 1][j + 1]) {
                        dp[i][j] = true;
                        count++;
                    }
                }
            }
        }
        return count;
    }

    //2.剑指 Offer II 034. 外星语言是否排序(请说个人话吧)
    public boolean isAlienSorted(String[] words, String order) {
        int[] map = new int[26];
        for(int i = 0; i < 26; i++) {
            map[order.charAt(i) - 'a'] = i;
        }
        for(int i = 0; i < words.length - 1; i++) {
            int len1 = words[i].length();
            int len2 = words[i + 1].length();
            int min = len1 > len2 ? len2: len1;
            int j = 0;
            for(; j < min; j++) {
                if(map[words[i].charAt(j) - 'a'] > map[words[i + 1].charAt(j) - 'a']) {
                    return false;
                }
                if(map[words[i].charAt(j) - 'a'] < map[words[i + 1].charAt(j) - 'a']) {
                    break;
                }
            }
            if(j == min && len1 > len2) {
                return false;
            }
        }
        return true;
    }

    //3.剑指 Offer II 015. 字符串中的所有变位词(滑动窗口 + 字典)
    public List<Integer> findAnagrams(String s, String p) {
        int lenS = s.length();
        int lenP = p.length();
        int[] mapS = new int[26];
        int[] mapP = new int[26];
        List<Integer> list = new ArrayList<>();
        if(lenS < lenP) {
            return list;
        }
        int windows = lenP;
        for(int i = 0; i < lenP; i++) {
            mapP[p.charAt(i) - 'a']++;
            mapS[s.charAt(i) - 'a']++;
        }
        for(int i = windows; i < lenS; i++) {
            if(Arrays.equals(mapP, mapS)) {
                list.add(i - windows);
            }
            mapS[s.charAt(i - windows) - 'a']--;
            mapS[s.charAt(i) - 'a']++;
        }
        if(Arrays.equals(mapP, mapS)) {
            list.add(lenS - windows);
        }
        return list;
    }

    //4.剑指 Offer II 105. 岛屿的最大面积(回溯)
    private int countMax;
    private int count;
    public int maxAreaOfIsland(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(grid[i][j] == 1) {
                    count = 0;
                    dfs(grid, i, j);
                    if(count > countMax) {
                        countMax = count;
                    }
                }
            }
        }
        return countMax;
    }

    private void dfs(int[][] grid, int x, int y) {
        if(x >= grid.length || y >= grid[0].length ||
                x < 0 || y < 0 || grid[x][y] == 0) {
            return;
        }
        grid[x][y] = 0;
        count++;
        dfs(grid, x - 1, y);
        dfs(grid, x + 1, y);
        dfs(grid, x, y - 1);
        dfs(grid, x, y + 1);
    }

//    //7.二维区域和检索 - 矩阵不可变(二维前缀和)
//    class NumMatrix {
//        //前缀和
//        private int[][] sum;
//        public NumMatrix(int[][] matrix) {
//            int x = matrix.length;
//            int y = x == 0 ? 0 : matrix[0].length;
//            this.sum = new int[x + 1][y + 1];
//            for(int i = 1; i <= x; i++) {
//                for(int j = 1; j <= y; j++) {
//                    sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
//                }
//            }
//        }
//
//        public int sumRegion(int row1, int col1, int row2, int col2) {
//            row1++;
//            col1++;
//            row2++;
//            col2++;
//            return sum[row2][col2] - sum[row1 - 1][col2] - sum[row2][col1 - 1] + sum[row1 - 1][col1 - 1];
//        }
//    }

    //8.剑指 Offer II 013. 二维子矩阵的和(二维前缀和)
    class NumMatrix {

        private int[][] arr;

        public NumMatrix(int[][] matrix) {
            int x = matrix.length;
            int y = x == 0 ? 0 : matrix[0].length;
            this.arr = new int[x + 1][y + 1];
            for(int i = 1; i <= x; i++) {
                for(int j = 1; j <= y; j++) {
                    arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + matrix[i - 1][j - 1];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            row1++;
            col1++;
            row2++;
            col2++;
            return arr[row2][col2] - arr[row1 - 1][col2] - arr[row2][col1 - 1] + arr[row1 - 1][col1 - 1];
        }
    }

    //9.剑指 Offer II 036. 后缀表达式(栈)
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < tokens.length; i++) {
            char ans = tokens[i].charAt(0);
            if(ans == '-' && tokens[i].length() > 1) {
                stack.push(Integer.parseInt(tokens[i]));
                continue;
            }
            int num1 = 0;
            int num2 = 0;
            switch(ans) {
                case '+':
                    stack.push(stack.pop() + stack.pop());
                    break;
                case '-':
                    num2 = stack.pop();
                    num1 = stack.pop();
                    stack.push(num1 - num2);
                    break;
                case '*':
                    stack.push(stack.pop() * stack.pop());
                    break;
                case '/':
                    num2 = stack.pop();
                    num1 = stack.pop();
                    stack.push(num1 / num2);
                    break;
                default :
                    stack.push(Integer.parseInt(tokens[i]));
            }
        }
        return stack.pop();
    }

//    //10.剑指 Offer II 060. 出现频率最高的 k 个数字(优先级队列 + 哈希表)
//    public int[] topKFrequent(int[] nums, int k) {
//        Map<Integer, Integer> map = new HashMap<>();
//        for(int i = 0; i < nums.length; i++) {
//            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
//        }
//        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return map.get(o1) - map.get(o2);
//            }
//        });
//        for(int i = 0; i < nums.length; i++) {
//            if(!queue.isEmpty() && queue.contains(nums[i])) {
//                continue;
//            }
//            if(queue.size() < k) {
//                queue.offer(nums[i]);
//            } else if(map.get(queue.peek()) < map.get(nums[i])) {
//                queue.poll();
//                queue.offer(nums[i]);
//            }
//        }
//        int[] ret = new int[k];
//        int index = 0;
//        for(int num : queue) {
//            ret[index++] = num;
//        }
//        return ret;
//    }

    //剑指 Offer II 060. 出现频率最高的 k 个数字(哈希优化)
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        List<Integer> list = new ArrayList<>(map.keySet());
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o2) - map.get(o1);
            }
        });
        int[] ret = new int[k];
        for(int i = 0; i < k; i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }


}

class Main {
    public static void main(String[] args) {
        int[] arr = {1,1,1,2,2,3};
        Solution solution = new Solution();
        solution.topKFrequent(arr, 2);
    }
}
